package hwOne3;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import org.w3c.dom.traversal.NodeIterator;

import java.util.Iterator;
import java.util.NoSuchElementException;

// 算法1.3先进先出队列
// 作业 1.3.15
public class Queue<Item> implements Iterable<Item>
{
    private Node first; // 指向最早添加的结点的链接
    private Node last;  // 指向最近添加的结点的链接
    private int N;       // 队列中的元素数量

    private class Node
    {  // 定义了结点的嵌套类
        Item item;
        Node next;
    }
    public boolean isEmpty() {  return first == null;  }  // 或： N == 0.
    public int size()         {  return N;  }
    public void enqueue(Item item)
    {  // 向表尾添加元素
        Node oldlast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if (isEmpty()) first = last;
        else            oldlast.next = last;
        N++;
    }
    public Item dequeue()
    {  // 从表头删除元素
        Item item = first.item;
        first = first.next;
        if (isEmpty()) last = null;
        N--;
        return item;
    }
    // 返回队首元素而不删除
    public Item peek() {
        if (isEmpty()) {
            throw new RuntimeException("Queue underflow");
        }
        return first.item; // 队首的值
    }
    // iterator()的实现请见算法1.4
    // 测试用例main()的实现请见前面
    public Iterator<Item> iterator() {
        return new NodeIterator();
    }

    // an array iterator, from first to last-1
    private class NodeIterator implements Iterator<Item> {
        private int i = 0;

        public boolean hasNext() {
            return i < N;
        }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = first.item;
            i++;
            return item;
        }
    }

    public static void main(String[] args) {
        // 从命令行读取 k
        if (args.length < 1) {
            StdOut.println("Usage: java KthLastString <k>");
            return;
        }
        int k = Integer.parseInt(args[0]);
        if (k <= 0) {
            throw new IllegalArgumentException("k must be greater than 0.");
        }

        // 创建一个Queue
        Queue<String> queue = new Queue<>();
        StdOut.println("Enter strings (press Ctrl+D to end input):");

        // 读取标准输入中的字符串
        while (!StdIn.isEmpty()) {
            String input = StdIn.readString();
            if ("***".equalsIgnoreCase(input)) { // 检查是否输入了 "***"
                break;
            }
            queue.enqueue(input);
            // 保持队列中的元素数量不超过 k
            if (queue.size() > k) {
                queue.dequeue(); // 移除队列最前面的元素
            }
        }

        // 队列的头部现在是倒数第 k 个字符串
        if (queue.size() == k) {
            StdOut.println("The " + k + "th last string is: " + queue.peek());
        } else {
            StdOut.println("Insufficient input. There are less than " + k + " strings.");
        }
    }
}